2018.4.25 leetcode中文官网用起~

今天开始用中文官网的leetcode了

Array - 581. 最短无序连续子数组

题目详情

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

你找到的子数组应是最短的，请输出它的长度。

示例1:

输入: [2, 5, 6, 4, 8, 11, 9, 10, 15]

输出: 5

解释: 你只需要对 [6, 4, 8, 10, 9]进行升序排序，那么整个表都会变为升序排序。

思路

• 当我们找到第一个违反ascending排序的数字 4的时候，我们不能是仅仅把beg 标记为4的前面一个数字6，而是要一直往前，找到一个合适的位置，找到在最前面位置的比4大的数字，这里是5。
• 同样的，为了找end，我们要从11的后面找，找比11小的数，这里是10
• 这样的话，范围就是5到10 是我们要找的子数组。把3到6排序完了之后，整个array 就已经是排序的了。
• 这里发现，这组无序数组中，4是最小值，11是最大值
• 所以，从左遍历的时候更新已遍历元素的当前最大值，当下一个元素小于最大值，那么更新end的值

具体代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var findUnsortedSubarray = function(nums) {
    let n = nums.length
    let beg = -1
    let end = -2
    let min = nums[n-1];
    let max = nums[0];

    for(let i=0; i < n; i++)
    {
        max = Math.max(max, nums[i]);
        min = Math.min(min, nums[n-1-i]);
        
        if(nums[i] < max) end = i;
        if(nums[n-1-i] > min) beg = n-1-i;
    }
    
    return end - beg + 1
};

由于这题用了不少时间… 所以今天就做一题好了